package Boogle_and_Word_Ladder;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NavigableSet;
import java.util.TreeSet;


public class Boggle {
	private static final NavigableSet<String> dictionary;
	static{
		dictionary = new TreeSet<String>();
		try{
			BufferedReader br = new BufferedReader(new FileReader("src/Boogle_and_Word_Ladder/1.txt"));
			String line;
			while((line=br.readLine())!=null){
				dictionary.add(line.split(":")[0]);
			}
		}
		catch(Exception e){
			throw new RuntimeException(e);
		}
	}
	
	private Boggle() {
		
	}
	
	public static List<String> solver(char[][] grid){
		if(grid==null)
			throw new NullPointerException("Empty");
		List<String> validWord = new ArrayList<String>();
		for(int i=0;i<grid.length;++i){
			for(int j=0;j<grid.length;++j)
//				helper(grid,i,j,"",validWord);
			
				helper(grid,i,j,grid[i][j]+"",validWord);
			//if we use the above line, will not have the single character words
		}
		
		return validWord;
	}
	
	public static void helper(char[][] grid, int i, int j, String pre, List<String> valid){
		assert grid != null;
		assert valid != null;
		
		for(int m = Math.max(0, i-1);m<Math.min(grid.length, i+2);++m){
			for(int n = Math.max(0, j-1); n<Math.min(grid[0].length, j+2); ++n){
				if(m!=i || n!=j){
					String word = pre + grid[m][n];
//					if(dictionary.contains(word) && !valid.contains(word))
				//the above line is the replacement of no single character words
					if(dictionary.contains(word))
						valid.add(word);
					if(dictionary.subSet(word, word+Character.MAX_VALUE).size() > 0)
						helper(grid,m,n,word,valid);
				}
			}	
		}
		
	}
	
	public static void main (String[] args){
		 char[][] board = { {'a', 'b', 'c', 'd' },  
                 {'n', 'x', 'p', 'q' },
                 {'k', 't', 'i', 'w' },
                 {'e', 'f', 'g', 's' },
              };
		 
		 List<String> ansList = Boggle.solver(board);
		 for(String s:ansList)
			 System.out.println(s);
	}
}
